package com.desin.modle.datastruct.algo.sorts13;

public class MyCountingSort {
    public void countSort(int[] arr,int n){
        int max = arr[0];
        for(int i=0;i<n;i++){
            if(arr[i]>max){
                max=arr[i];
            }
        }

        int[] c = new int[max+1];
        for(int i=0;i<n;i++){
            c[arr[i]]=c[arr[i]]+1;
        }

        for(int i=1;i<c.length;i++){
            c[i] = c[i]+c[i-1];
        }

        int[] re = new int[n];
        for(int i=n-1;i>=0;i--){
            int index = c[arr[i]] - 1;
            re[index]=arr[i];
            c[arr[i]]--;
        }

        for(int i=0;i<n;i++){
            arr[i]=re[i];
        }
    }
}
